1. Field of the Invention
The present invention relates to the decoding of Reed-Solomon codes. More particularly, the present invention relates to a method and an apparatus for fast decoding of Reed-Solomon codes.
2. The Prior Art
Reed-Solomon (RS) codes are used in many different applications, but one of their most popular uses is in data transmission. Through the use of an RS encoder, data can be converted to an RS code, transmitted over a data communications medium, and then decoded on the receive side by an RS decoder, which can then correct errors encountered during transit. This technique has a wide variety of uses, including cable modems and satellite transmissions.
Cable modems are devices that work in a similar manner to the typical computer modems (which transmit data over telephone lines), except that they use cable television lines for the transmission. Due to the higher bandwidth capability of cable lines, cable modems are capable of much higher data transfer speeds than phone lines. With the increased popularity of the Internet, high speed data transmission lines are becoming more and more important in the marketplace. Cable modems have emerged as one of the leading forms of Internet communication.
Most cable modems contain two pieces of equipment for dealing with RS codes: an RS encoder and an RS decoder. Data to be sent is first separated into sequences of bytes with equal lengths. Most cable modems in use today split the data into sequences 122 bytes in length. Each of these sequences is known as a word. Each word is then passed through the RS encoder, which translates it into a Reed-Solomon codeword with a length of 128 bytes. Typical Reed-Solomon codewords have a length of 127 bytes. However, cable modem systems generally add an extra redundant bit (called an extended bit) to increase the error-correcting capability. This codeword can then be transmitted through the cable to the recipient. During this transmission, however, interference can sometimes change the encoded data so that it arrives at its destination in a distorted form. These changes in the data are known as errors. When the codeword reaches the RS decoder, it oftentimes will have to not only be decoded, but error-corrected as well.
In order to correct errors that occurred during transmission, the error positions (which bytes were affected) as well as the error values (how each byte was affected) must be determined. The prior art techniques for decoding and error-detection are based on either a Berlekamp-Massey algorithm or a Euclidean algorithm. These algorithms generally represent the RS codeword as a polynomial. Syndromes of this polynomial can then be found. Syndromes are parity check equations that will eventually be used to find the error locations and values. The drawback of these techniques is that they attempt to find the number of errors and their positions without knowledge of the specific error correcting capability of the code.
Reed-Solomon codes have a specific error correcting capability based on the length of the code. The number of bytes in a codeword can be represented by the formula: EQU #of bytes=2.sup.d +n
Where minimum distance d is the largest number that can satisfy this equation when n is zero or a positive integer.
Thus, a code of length 127 bytes, has a minimum distance of 6 (127=2.sup.6 +63). The error-correcting capability a RS code can then be determined by the formula: ##EQU1## where t is the largest whole number which satisfies this equation and represents the error-correcting capability of an RS code with minimum distance d.
Therefore, the codeword of length 127 bytes has an error correcting capability of 2, meaning that at most 2 errors can be corrected in a RS codeword of length 127 bytes. Simply by adding one more byte (for a total of 128), the error correcting capability can be increased to 3. This is why cable modem systems use extended Reed-Solomon codes (having the extended bit) rather than normal Reed-Solomon codes.
The main drawback of the prior art decoders is that they use methods that are designed for codes with relatively high error correcting capabilities (t&gt;3). For codes with an error correcting capabilities of 3 or less, the prior art methods are too complex to implement in a truly time effective manner. What is needed is a fast technique to decode and detect errors in codes with error correcting capabilities of 3 or less.